package com.practice.niuke.new_direct_basics.class15;

import java.util.HashMap;

/**
 * 机K器MP人算达法到扩指展定题位目置二方法数
 * 【题目】
 * 假设有排成一行的 N 个位置， 记为 1~N， N 一定大于或等于 2。 开始时机器人在其中的 M 位
 * 置上(M 一定是 1~N 中的一个)， 机器人可以往左走或者往右走， 如果机器人来到 1 位置， 那
 * 么下一步只能往右来到 2 位置;如果机器人来到 N 位置， 那么下一步只能往左来到 N-1 位置。
 * 规定机器人必须走 K 步， 最终能来到 P 位置(P 也一定是 1~N 中的一个)的方法有多少种。 给
 * 定四个参数 N、 M、 K、 P， 返回方法数。
 * 【举例】
 * N=5,M=2,K=3,P=3
 * 上面的参数代表所有位置为 1 2 3 4 5。 机器人最开始在 2 位置上， 必须经过 3 步， 最后到
 * 达 3 位置。 走的方法只有如下 3 种: 1)从2到1， 从1到2， 从2到3 2)从2到3， 从3到2， 从2到3
 * 3)从2到3， 从3到4， 从4到3
 * 所以返回方法数 3。 N=3,M=1,K=3,P=3
 * 上面的参数代表所有位置为 1 2 3。 机器人最开始在 1 位置上， 必须经过 3 步， 最后到达 3
 * 位置。 怎么走也不可能， 所以返回方法数 0。
 */
public class Code01_RobotWalk {

    /**
     * （2）使用暴力递归方法求解（机器人走法数）的主流程函数（TODO：暴力递归主函数）
     *
     * @param N     位置为1 ~ N，固定参数
     * @param start 机器人开始的位置是start
     * @param K     总共可以走K步
     * @param P     最终目标位置是P，固定参数
     * @return int
     */
    public static int ways1(int N, int start, int K, int P) {
        // 参数无效直接返回0
        if (N < 2 || K < 1 || start < 1 || start > N || P < 1 || P > N) {
            return 0;
        }
        // 总共N个位置，从start点出发，还剩K步，返回最终能达到P的方法数
        return walk(N, start, K, P);
    }

    /**
     * （1）该函数的含义：只能在1~N这些位置上移动，当前在cur位置，走完rest步之后，停在P位置的方法数作为返回值返回
     * （暴力递归的机器人走法）
     *
     * @param N    位置为1 ~ N，固定参数
     * @param cur  当前来到的位置是cur，可变参数
     * @param rest 还剩res步没有走，且必须走完，可变参数
     * @param P    最终目标位置是P，固定参数
     * @return int
     */
    public static int walk(int N, int cur, int rest, int P) {
        // 如果没有剩余步数了，当前的cur位置就是最后停留的位置
        // 如果最后的位置停在P上，那么之前做的移动是有效的
        // 如果最后的位置没在P上，那么之前做的移动是无效的
        if (rest == 0) {
            return cur == P ? 1 : 0;
        }
        // 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
        // 后续的过程就是，来到2位置上，还剩rest-1步要走
        if (cur == 1) {
            return walk(N, 2, rest - 1, P);
        }
        // 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
        // 后续的过程就是，来到N-1位置上，还剩rest-1步要走
        if (cur == N) {
            return walk(N, N - 1, rest - 1, P);
        }
        // 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
        // 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
        // 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
        // 走向左、走向右是截然不同的方法，所以总方法数要都算上
        return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
    }

    /**
     * （3）“暴力递归方法”改为“记忆化搜索”（TODO：记忆化搜索主函数）
     * 求解（机器人走法数）的主流程函数
     *
     * @param N     位置为1 ~ N，固定参数
     * @param start 机器人开始的位置是start
     * @param K     总共可以走K步
     * @param P     最终目标位置是P，固定参数
     * @return int
     */
    public static int waysCache1(int N, int start, int K, int P) {
        // 参数无效直接返回0
        if (N < 2 || K < 1 || start < 1 || start > N || P < 1 || P > N) {
            return 0;
        }
        // 对于f函数而言，当cur和rest确定了，返回值一定是确定的，因此可以用缓存记录下每一组"cur"_"rest"的结果，
        // 缓存
        // f(2, 3) - v   ---->   key:"2"_"3" value:v
        HashMap<String, Integer> cache = new HashMap<>();
        // 总共N个位置，从start点出发，还剩K步，返回最终能达到P的方法数
        return f1(N, start, K, P, cache);
    }

    /**
     * （4）“暴力递归方法”改为“记忆化搜索”
     * 当cur和rest确定了，返回值一定是确定的
     *
     * @param N     位置为1 ~ N，固定参数
     * @param cur   当前来到的位置是cur，可变参数
     * @param rest  还剩res步没有走，且必须走完，可变参数
     * @param P     最终目标位置是P，固定参数
     * @param cache 记录下每一组"cur"_"rest"结果的缓存
     * @return int
     */
    public static int f1(int N, int cur, int rest, int P, HashMap<String, Integer> cache) {

        // 当前的cur和rest组成的在缓存中的key
        String key = String.valueOf(cur) + "_" + String.valueOf(rest);
        // 缓存中记录过当前的cur和rest所计算出来的结果，直接返回。
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        // 缓存中没有记录过当前的cur和rest所计算出来的结果。
        int ans = 0;
        // 如果没有剩余步数了，当前的cur位置就是最后停留的位置
        // 如果最后的位置停在P上，那么之前做的移动是有效的
        // 如果最后的位置没在P上，那么之前做的移动是无效的
        if (rest == 0) {
            ans = cur == P ? 1 : 0;
            // 记录到缓存中
            cache.put(key, ans);
            return ans;
        }
        // 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
        // 后续的过程就是，来到2位置上，还剩rest-1步要走
        if (cur == 1) {
            ans = f1(N, 2, rest - 1, P, cache);
            // 记录到缓存中
            cache.put(key, ans);
            return ans;
        }
        // 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
        // 后续的过程就是，来到N-1位置上，还剩rest-1步要走
        if (cur == N) {
            ans = f1(N, N - 1, rest - 1, P, cache);
            // 记录到缓存中
            cache.put(key, ans);
            return ans;
        }
        // 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
        // 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
        // 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
        // 走向左、走向右是截然不同的方法，所以总方法数要都算上
        ans = f1(N, cur + 1, rest - 1, P, cache) + f1(N, cur - 1, rest - 1, P, cache);
        // 记录到缓存中
        cache.put(key, ans);
        return ans;
    }

    /**
     * （5）“暴力递归方法”改为“动态规划”（TODO：动态规划的主函数）
     * 求解（机器人走法数）的主流程函数
     *
     * @param N     位置为1 ~ N，固定参数
     * @param start 机器人开始的位置是start
     * @param K     总共可以走K步
     * @param P     最终目标位置是P，固定参数
     * @return int
     */
    public static int waysCache2(int N, int start, int K, int P) {
        // 参数无效直接返回0
        if (N < 2 || K < 1 || start < 1 || start > N || P < 1 || P > N) {
            return 0;
        }
        // 对于f函数而言，当cur和rest确定了，返回值一定是确定的，因此可以用缓存记录下每一组"cur"_"rest"的结果，
        // 变化参数(cur, rest)，
        // cur的变化范围是1 ~ N
        // rest的变化范围是0 ~ K
        // 缓存结构用一个二维（两个变化参数）数组,
        // （二维数组中cur的变化范围是0~N, 但是我们在初始化之后，后面的计算过程中，没有设置cacahe[0][?]的情况，第0行不用）
        int[][] cache = new int[N + 1][K + 1];
        for (int i = 0; i < cache.length; i++) {
            for (int j = 0; j < cache[0].length; j++) {
                // 给cache的每个位置赋初始值，-1表示这个位置没有被计算过
                // （之所以用-1而不用0，是因为0也是我后面的计算结果之一）
                cache[i][j] = -1;
            }
        }
        // 总共N个位置，从start点出发，还剩K步，返回最终能达到P的方法数
        return f2(N, start, K, P, cache);
    }

    /**
     * （6）“暴力递归方法”改为“动态规划”
     * 当cur和rest确定了，返回值一定是确定的
     *
     * @param N     位置为1 ~ N，固定参数
     * @param cur   当前来到的位置是cur，可变参数
     * @param rest  还剩res步没有走，且必须走完，可变参数
     * @param P     最终目标位置是P，固定参数
     * @param cache 记录下每一组"cur"_"rest"结果的缓存
     * @return int
     */
    public static int f2(int N, int cur, int rest, int P, int[][] cache) {

        // 当前的cur和rest组成的在缓存中的key
        String key = String.valueOf(cur) + "_" + String.valueOf(rest);
        // 缓存中记录过当前的cur和rest所计算出来的结果，直接返回。
        if (cache[cur][rest] != -1) {
            return cache[cur][rest];
        }
        // 缓存中没有记录过当前的cur和rest所计算出来的结果。
        int ans = 0;
        // 如果没有剩余步数了，当前的cur位置就是最后停留的位置
        // 如果最后的位置停在P上，那么之前做的移动是有效的
        // 如果最后的位置没在P上，那么之前做的移动是无效的
        if (rest == 0) {
            ans = cur == P ? 1 : 0;
            // 记录到缓存中
            cache[cur][rest] = ans;
            return ans;
        }
        // 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
        // 后续的过程就是，来到2位置上，还剩rest-1步要走
        if (cur == 1) {
            ans = f2(N, 2, rest - 1, P, cache);
            // 记录到缓存中
            cache[cur][rest] = ans;
            return ans;
        }
        // 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
        // 后续的过程就是，来到N-1位置上，还剩rest-1步要走
        if (cur == N) {
            ans = f2(N, N - 1, rest - 1, P, cache);
            // 记录到缓存中
            cache[cur][rest] = ans;
            return ans;
        }
        // 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
        // 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
        // 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
        // 走向左、走向右是截然不同的方法，所以总方法数要都算上
        ans = f2(N, cur + 1, rest - 1, P, cache) + f2(N, cur - 1, rest - 1, P, cache);
        // 记录到缓存中
        cache[cur][rest] = ans;
        return ans;
    }

    /**
     * （7）依赖分析过程，直接的动态规划方法（TODO：直接一步到位为动态规划）
     *
     * @param N     位置为1 ~ N，固定参数
     * @param start 机器人开始的位置是start
     * @param K     总共可以走K步
     * @param P     最终目标位置是P，固定参数
     * @return int
     */
    public static int waysdp(int N, int start, int K, int P) {
        // 无效参数判断
        if (N < 2 || K < 1 || start < 1 || start > N || P < 1 || P > N) {
            return 0;
        }
        // 动态规划表
        int[][] dp = new int[N + 1][K + 1];
        // 第0列填好（根据base case）
        dp[P][0] = 1;// 第0列其他位置就是0，与数组初始值一样，不用重复再赋值0。
        // 由第一列（base case确定的）去求解其他的列
        for (int col = 1; col <= K; col++) {
            // 第一行(依赖于，第2行的前一列的数，左下角)
            dp[1][col] = dp[2][col - 1];
            // 最后一行(依赖于，第N-1行的前一列的数，左上角)
            dp[N][col] = dp[N - 1][col - 1];
            // 普通的行
            for (int row = 2; row < N; row++) {
                // (同时依赖于，上一行的前一列的数，左上角；下一行的前一列的数，左下角；)
                dp[row][col] = dp[row - 1][col - 1] + dp[row + 1][col - 1];
            }
        }
        // 看主函数怎么调用的
        return dp[start][K];
    }


    public static void main(String[] args) {
        System.out.println(ways1(7, 4, 9, 5));
        System.out.println(waysCache1(7, 4, 9, 5));
        System.out.println(waysCache2(7, 4, 9, 5));
        System.out.println(waysdp(7, 4, 9, 5));
    }

}
